local pairs        = pairs
local setmetatable = setmetatable
local getmetatable = getmetatable

--override has for use lists
function has(list,v)  -->Check if a list has a value
  local i,t
  local list = list
  if type(list) == "list" then
    list = list.__list
  end
  for i,t in pairs(list) do
    if t == v then 
      return t 
    end
  end
  return nil
end

module(...) -->name the package according to the filename

function entries (t)
  local __iter = t.__list.first
  local __end = t.__list.last
  return function ()
           if __iter <= __end then 
             __iter = __iter + 1
             return t.__list[__iter-1] 
           end
         end
end

list_mt = {
  __type = "list",
  pushleft = function(self, value)
    local first = self.__list.first - 1
    self.__list.first = first
    self.__list[first] = value
  end,
  pushright = function(self, value)
    local last = self.__list.last + 1
    self.__list.last = last
    self.__list[last] = value
  end,
  popleft = function(self)
    local first = self.__list.first 
    if first > self.__list.last then
      error("list is empty") 
    end
    local value = self.__list[first]
    self.__list[first] = nil        -- to allow garbage collection
    self.__list.first = first + 1 
    return value
  end,
  popright = function(self)
    local last = self.__list.last
    if self.__list.first > last then 
      error("list is empty") 
    end
    local value = list[last] 
    self.__list[last] = nil         -- to allow garbage collection
    self.__list.last = last - 1
    return value
  end,
  foreach = function(self,functor)
    for v in entries(self) do 
      functor(v)
    end
  end,
  __index = function(t,k)
    return getmetatable(t)[k]
  end,
}

new = function(t)
  local l={__list = {first = 0, last = -1}} 
  if t then
    for k,v in pairs(t) do
      l[k]=v
    end
  end
  setmetatable(l,list_mt)
  return l
end

